    package practice1_100;

    import java.lang.reflect.Array;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.TreeSet;

    public class Practice15 {
        public List<List<Integer>> threeSum(int[] nums) {
            if(nums.length<=2) return new ArrayList<>();
            if(nums.length==3 && nums[0]+nums[1]+nums[2]==0) {
               List<List<Integer>>  list= new ArrayList<>();
               List<Integer> list1 =new ArrayList<>();
                list1.add(nums[0]);
                list1.add(nums[1]);
                list1.add(nums[2]);
                list.add(list1);
                return list;
            }

            quick_sort(nums,0,nums.length-1);
            Arrays.sort(nums);
            List<List<Integer>> listAll= new ArrayList<>();
            for(int i=0;i<nums.length-2;i++){//第一个指针
                if(i>0&& nums[i]==nums[i-1]) continue;
                for (int j=i+1, o=nums.length-1;j<o;){//双指针在已排序数组的第二，和末尾位置
                    //跳过重复值
                    if(nums[j]==nums[j+1]) {
                        j++;continue;
                    }
                    if(nums[o]==nums[o-1]){
                        o--;continue;
                    }
                    if(nums[i]+nums[j]+nums[o]>0){
                        o--;
                    }else if(nums[i]+nums[j]+nums[o]<0){
                        j++;
                    }else {
                        List<Integer> integerList=new ArrayList<>();
                        integerList.add(nums[i]);
                        integerList.add(nums[j]);
                        integerList.add(nums[o]);
                        listAll.add(integerList);
                        o--;
                        j++;
                    }
                }
          }

    //        for (int i=0;i<nums.length-2;i++){
    //            for(int j=i+1;j<nums.length-1;j++){
    //                for(int o=nums.length-1;o>j;o--){
    //                    if (nums[i]+nums[j]+nums[o]==0){
    //                        List<Integer> list=new ArrayList<>();
    //                        list.add(nums[i]);
    //                        list.add(nums[j]);
    //                        list.add(nums[o]);
    //                        listAll.add(list);
    //                    }
    //                }
    //            }
    //        }
            return listAll;
        }


        //快排算法
        public void quick_sort(int s[], int l, int r)
        {
            if (l < r)
            {
                //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
                int i = l, j = r, x = s[l];
                while (i < j)
                {
                    while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                        j--;
                    if(i < j)
                        s[i++] = s[j];

                    while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                        i++;
                    if(i < j)
                        s[j--] = s[i];
                }
                s[i] = x;
                quick_sort(s, l, i - 1); // 递归调用
                quick_sort(s, i + 1, r);
            }
        }

        public List<List<Integer>> threeSum1(int[] nums) {
            Arrays.sort(nums);
            TreeSet<String > set=new TreeSet<>();
            List<List<Integer>> list=new ArrayList<> ();
            if(nums.length<=2)return  list;
            for(int left=0;left<nums.length-2;left++){
                if(nums[left]>0) return list;
                int mid=left+1,right=nums.length-1;
                while(mid<right){
                    //if(nums[right]<0) return list;
                    if(nums[left]+nums[mid]+nums[right]==0&&!set.contains(nums[left]+","+nums[mid]+","+nums[right])){
                        set.add(nums[left]+","+nums[mid]+","+nums[right]);
                        list.add(new ArrayList(Arrays.asList(new Integer[] {nums[left],nums[mid],nums[right]})));
                        while(mid<right&&nums[mid]==nums[mid+1])
                            mid=mid+1;
                        while(mid<right&&nums[right]==nums[right-1])
                            right=right-1;
                    }else if(nums[left]+nums[mid]+nums[right]>0){
                        right--;
                    }else if(nums[left]+nums[mid]+nums[right]<0){
                        mid++;
                    }

                }
            }
            return list;
        }



        public static void main(String[] args) {
            int[] array1=new int[] {-1,0,1,2,-1,-4};
            int[] array2=new int[] {-2,0,0,2,2};


            int[] array= new int[] {1,3,4,623,3,324,43,-58,-51,48,-50,43,65,265,62,42,23,34,2,2};
            List<List<Integer>> list=   new Practice15().threeSum1(array2);

            }

    }
